#pragma once

class BKDRHash
{
    size_t operator()(const string& str)
    {
        size_t hash = 0;
        for(auto ch : str)
        {
            hash = hash * 131 + ch;      
        }
        return hash;
    }
};


class APHash
{
    size_t operator()(const string& str)
    {
        register size_t hash = 0;
        size_t i = 0;
        for (auto ch : str)
        {
            if ((i & 1) == 0)
            {
                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
            }
        }
        return hash;
    }
};

class RSHash
{
    size_t operator()(const string& str)
    {
        size_t hash = 0;
        size_t magic = 63689;
        for(auto ch : str)
        {
            hash = hash * magic + ch;
            magic *= 378551;
        }
        return hash;
    }
};


template<size_t N,class K = string,class hash1 = BKDRHash,class hash2 = APHash,class hash3 = RSHash>
class BloomFilter
{
    void set(size_t x)
    {
        size_t hash1 = BKDRHash()(x);
        _bs.set(hash1);

        size_t hash2 = APHash()(x);
        _bs.set(hash2);

        size_t hash3 = RSHash()(x);
        _bs.set(hash3);
    }

    bool test(size_t x)
    {
        size_t hash1 = BKDRHash()(x);
        if (!_bs.test(hash1))
            return false;

        size_t hash2 = APHash()(x);
        if (!_bs.test(hash2))
            return false;

        size_t hash3 = RSHash()(x);
        if (!_bs.test(hash3))
            return false;
        return true;
    }






private:
	bitset<N * 5> _bs;
};